package class06_heap;


import java.util.PriorityQueue;

public class Test04_SortArrayDistanceLessK {

    /**
     * 一个无序数组，但是每一个元素调整距离不超过K，就会将这个数组调整为有序；
     * 现在来调整一下这个数组：
     * 整体实现思路：将arr元素放入到一个heapSize为k的小根堆中，通过不断的pop小根堆和push小根堆，依次获取最小元素进行排序
     */
    public void sortArrayDistanceLessK(int[] arr, int k) {
        // 边界条件判断；
        if (arr == null || arr.length < 2 || k == 0) {
            return;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        //将前k-1个元素添加到 heap中，或者将所有数组元素放入堆中
        int index = 0;
        for (; index < Math.min(arr.length - 1, k - 1); index++) {
            heap.add(index);
        }
        // 如果之前是将前k-1个元素添加到heap中，那么会进入该循环，如果是将整个数组添加到heap中，那么不会进如该循环
        int i = 0;
        for (; index < arr.length; i++, index++) {
            heap.add(arr[index]);
            arr[i] = heap.poll();
        }
        // 将heap中剩余的元素，依次添加进数组中
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }

    }
}
